package org.chengn.level_middle.context1466;

import java.util.*;

/**
 * @Title: Context1466
 * @Author ChengN
 * @Package org.chengn.level_middle.context1466
 * @Date 2023/12/7 0:58
 * @description: 重新规划路线
 */
public class Context1466 {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] list = new List[n];
        for (int i = 0; i < n; ++i) {
            list[i] = new ArrayList<>();
        }

        for (int[] conn : connections) {
            list[conn[1]].add(new int[]{conn[0], 1});
            list[conn[0]].add(new int[]{conn[1], -1});
        }

        int res = 0;

        Set<Integer> nodes = new HashSet<>();
        Queue<Integer> queue = new ArrayDeque<>(n);
        queue.add(0);
        nodes.add(0);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            List<int[]> des = list[node];
            for (int[] de : des) {
                if (nodes.contains(de[0])) continue;
                nodes.add(de[0]);
                queue.add(de[0]);
                if (de[1] == -1) res++;
            }
        }

        return res;

    }
}
